package Day1;

import java.util.Scanner;

/**
 * @projectName: AutumnTest
 * @package: Day1
 * @className: longestPalindrome
 * @author: Tongxinxin
 * @description: 最长回文子串
 * @date: 2025/8/25 18:43
 * @version: 1.0
 */
public class longestPalindrome {
    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();

        int n = chars.length;
        if (n == 1) {
            return s;
        }

        // 定义数组，用来标识从i到j这段字符串是否是回文串
        boolean[][] dp = new boolean[n][n];

        // 定义最长回文串的长度及初始索引
        int maxLen = 1;
        int begin = 0;

        // 初始化，每个字符都是一个回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }

        // 从长度2开始，循环遍历回文串的长度，最长到n,即整个字符串就是一个回文串
        for (int length = 2; length <= n; length++) {

            // 从第一个字符开始，i表示起始索引
            for (int i = 0; i < n; i++) {
                // j表示结束索引
                int j = i + length - 1;

                // 右边界索引不能超过字符串的最大长度
                if (j > n - 1) {
                    break;
                }

                // 如果两端字符不相等，肯定不是回文串
                // 如果两端相等，也不能表示这段一定是回文串，因为中间的字符串不一定是回文串
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    // 如果两端是相邻的字符串或者中间只间隔一个字符，那么这段就是回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        // 这段是不是，取决于内层是不是，比如abcda,dp[0][4]是不是取决于dp[1][3]是不是
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 如果dp[i][j]是回文串，且长度比maxlen大，那么就是当前最长的回文串
                if (dp[i][j] && length > maxLen) {
                    maxLen = length;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }

    public static void main(String[] args) {
        longestPalindrome solution=new longestPalindrome();
        String s1 = "babad";
        System.out.println("输入: " + s1);
        System.out.println("输出: " + solution.longestPalindrome(s1));

        String s2 = "cbbd";
        System.out.println("输入: " + s2);
        System.out.println("输出: " + solution.longestPalindrome(s2));

        String s3 = "babad";
        System.out.println("输入: " + s3);
        System.out.println("输出: " + solution.longestPalindrome(s3));
    }
}
